package bin_tree.leetcode;

/**
 * 将BST转为双向链表
 * @author yuisama
 * @date 2022/02/24 20:57
 **/
public class NowCoder_ConvertTree {
    /**
     * 传入一颗以pRoot为根的BST就能转为双向链表，返回链表的头节点
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        // 对树进行中序遍历
        // 此时的遍历 => 转换操作 =》先将左子树转为双向链表
        // 通过子函数就转了Convert(root.left);
        // 此时leftHead就是左链表的头节点
        TreeNode leftHead = Convert(pRootOfTree.left);
        // 继续处理根节点
        // 左子树的尾节点的next(right) = root
        // 根节点的前驱要链接左子树的尾节点 root.prev(left) = leftTail
        // 找到左链表的尾节点
        TreeNode leftTail = leftHead;
        // 注意判空
        while (leftTail != null && leftTail.right != null) {
            leftTail = leftTail.right;
        }
        // 此时leftTail就处在左侧链表的尾节点
        if (leftTail != null) {
            pRootOfTree.left = leftTail;
            leftTail.right = pRootOfTree;
        }
        // 再递归处理右子树，转换右子树为链表，返回右侧链表的头节点
        TreeNode rightHead = Convert(pRootOfTree.right);
        // 再和根节点拼接
        if (rightHead != null) {
            pRootOfTree.right = rightHead;
            rightHead.left = pRootOfTree;
        }
        // 返回整个大链表的根节点
        // 左树不为空返回左侧头节点
        // 否则返回根节点
        return leftHead == null ? pRootOfTree : leftHead;
    }
}